package data_structure.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *  * 1.求单链表中结点的数量
 *  * 2.查找单链表中倒数第k个结点【新浪面试题】
 *  * 3.单链表的反转【腾讯面试题】
 *    4. 从尾到头打印单链表（百度面试题）
 *    5. 合并两个有序单链表，合并之后，依然有序
 */
class LinkedListCountDemo {
    private static Node head;
    public static int size = 0;


    /**
     * 测试：遍历
     */
    public static void selectList(LinkedListCountDemo list){
        Node temp = list.head;
        System.out.println(temp.next);
        while (temp.next != null){
            System.out.println("遍历: "+temp);
            temp = temp.next;
        }
    }



    /**
     * 4.从尾到头打印单链表（百度面试题）
     */
    public void selectEndWith(){
        Stack<Object> stack = new Stack<>();
        Node temp = head;
        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }

    /**
     * 3.单链表的反转【腾讯面试题】bug
     */
    public void reverseList(){
       if (head == null){
           System.out.println("链表为空...");
           return;
       }
       Node headNew = new Node(0);
       int index = 1;
       Node temp = headNew;
       while (index <= size){
           Node node = selectEndIndex(index);
           node.next = null;
//           System.out.println("测试: "+node);
//           System.out.println("测试下一个指针: "+node.next);
           temp.next = node;
           temp = temp.next;
//           System.out.println("测试2: "+temp);
           index++;
       }
       //备份
//       Node headNew = head;
       head = null;
       head = headNew.next;
    }

    /**
     * 2.查找单链表中倒数第k个结点【新浪面试题】
     */
    public Node selectEndIndex(int index){
        if (index > size){
            System.out.println("位置不存在...");
            return null;
        }
        if (head == null){
            System.out.println("链表为空...");
            return null;
        }else {
            Node temp = head;
            int tempIndex = 0;
            while (tempIndex < (size - index) && temp != null){
                temp=temp.next;
                tempIndex++;
            }
//            System.out.println(temp);
            return temp;
        }
    }

    /**
     * 遍历
     */
    public void select(){
        if (head == null){
            System.out.println("链表为空...");
        }else {
            Node temp = head;
            while (temp != null){
                System.out.println(temp);
                temp = temp.next;
            }
            System.out.println("当前结点数量: "+size);
        }
    }

    /**
     * 添加结点
     */
    public void insert(Node node){
        if (head == null) {
            head = node;
        }
        else{
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
        size++;
    }

    /**
     * 创建单链表
     */
    static class Node{
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value='" + value + '\'' +
                    '}';
        }
    }

    public static void main(String[] args) {
        LinkedListCountDemo list = new LinkedListCountDemo();
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        Node n8 = new Node(8);
        list.insert(n1);
        list.insert(n5);
        list.insert(n3);
        list.insert(n2);
        //1.求单链表中结点的数量
        list.select();
        //2.查找单链表中倒数第k个结点【新浪面试题】
        System.out.println(list.selectEndIndex(1));
        //3.单链表的反转【腾讯面试题】
        System.out.println("单链表反转...");
        list.reverseList();
        list.select();
        System.out.println("百度面试题 反向输出");
        list.selectEndWith();
        System.out.println("新链表...");
        LinkedListCountDemo list1 = new LinkedListCountDemo();
        list1.insert(n4);
        list1.insert(n6);
        list1.insert(n8);
        list1.insert(n7);
        list1.select();
    }

}


